Multiprocessor systems are becoming more widespread in the computer industry. As such, parallel execution of code in the multiprocessors can be used to take advantage of performance gains. To optimize performance on multiprocessors, software programs need to be parallelized to take full advantage of the available parallel execution.
Generally, loops in a software program take additional time in the execution of a program. A technique to reduce this time is loop transformation. Loop transformations are used to increase the parallelism of the software program in modern compilers. Currently, there are many kinds of loop transformations, such as fusion, fission, blocking, shifting, greatest common divisor (GCD) transformation and affine partitioning.
Loop shifting, in particular, involves moving operations from one iteration of the loop body to a different iteration of the loop body. It does this by shifting a set of operations from the beginning of the loop body to the end of the loop body. A copy of these operations is also placed in the loop head or prologue. Loop shifting shifts a set of operations one at a time, thereby exposing just as much parallelism as can be exploited by the available resources. Parallelizing transformations can then operate on the shifted operations to further compact the loop body. Loop shifting can expose parallelism in order to increase the performance, area, and resource utilization of a multiprocessor.